import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

class Solution02 {
    // 创建一个哈希表，进行标记
    Set<String> hashSet = new HashSet<>();

    public int minMutation(String startGene, String endGene, String[] bank) {
        // 创建哈希表，将基因库数组进行装换
        Set<String> hashSetBank = new HashSet<>();
        for (String str : bank) {
            hashSetBank.add(str);
        }
        // 创建基因序列字符数组
        char[] tmp = { 'A', 'C', 'G', 'T' };
        // 处理边界条件
        if (startGene.equals(endGene)) {
            return 0;
        }
        if (!hashSetBank.contains(endGene)) {
            return -1;
        }
        // 创建一个队列
        Queue<String> q = new LinkedList<>();
        // 起始位置入队
        q.add(startGene);
        // 队头元素进行标记
        hashSet.add(startGene);
        // 定义一个变量记录结果
        int ret = 0;
        // 循环判断
        while (!q.isEmpty()) {
            // 看队列里面有几个元素
            int size = q.size();
            ret++;
            // 进行循环判断
            for (int i = 0; i < size; i++) {
                // 弹出队头元素
                String s = q.poll();
                // 对该字符串进行字符一一替换
                char[] ch = s.toCharArray();
                for (int j = 0; j < ch.length; j++) {
                    for (int k = 0; k < tmp.length; k++) {
                        // 标记原来的字符
                        char a = ch[j];
                        // 替换
                        ch[j] = tmp[k];
                        // 转换为字符串
                        String string = new String(ch);
                        // 判断基因库中是否存在
                        if (hashSetBank.contains(string) && !hashSet.contains(string)) {
                            // 再一次进行判断
                            if (endGene.equals(string)) {
                                return ret;
                            }
                            // 加入队列
                            q.add(string);
                            // 加入标记数组
                            hashSet.add(string);
                        }
                        // 还原
                        ch[j] = a;
                    }
                }
            }
        }
        return -1;
    }
}